백준 2579 계단 오르기

백준 2579 계단 오르기는 전형적인 dp 문제이다. 이 문제에서의 조건은 돌을 올라가는데 연속 3개의 계단을 밟을 수 없고 계단을 오를때는 1점프 혹은 2점프밖에 할 수 없다는 것이다. 그리고 마지막 계단에 왔을 때 밟아온 계단의 점수를 최대화 하는 것이 문제이다.

이 문제의 핵심은 연속 3개의 계단을 밟을 수 없다는 것이다. 즉 1 2 3 4 라는 계단이 있을 때 4라는 계단에 도달하기 위해서는

1 -> 3 -> 4 (이전 계단을 밟았을 경우 연속 3개를 밟지 못하므로 무조건 2점프를 뛰어야한다)

2-> 4 (이전 계단을 밟지 않았을 경우 조건에 상관없이 2계단 전까지의 최대합을 더해주면 된다.)

즉 dp [i] = max( dp[i-2] + arr[i], dp[i-3] + arr[i-1]+ arr[i] )라는 점화식으로 최대값을 구할 수 있다.

#pragma warning(disable:4996)

#include <cstdio>
#include <vector>
#include <string.h>
#define INF 987654321

using namespace std;

int n;
int arr[301];
int dp[301];

int max(int a, int b)
{
	return a > b ? a : b;
}

int main(int argc, char* argv[]) {

	//freopen("input.txt", "r", stdin);
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d", &arr[i]);

	for (int i = 1; i <= n; i++)
	{
		if (i == 1)
			dp[1] = arr[1];
		if (i == 2)
			dp[2] = arr[1]+arr[2];
		if (i >= 3)
			dp[i] = max(dp[i - 2] + arr[i], dp[i - 3] + arr[i-1] + arr[i]);
	}

	printf("%d\n", dp[n]);
	return 0;
}